#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool hasPathSum(TreeNode *root, int sum) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!root)
        return false;

    // leaf
    if(!root->left && !root->right){
        if(root->val == sum)
            return true;
        else
            return false;
    }

    // not leaf
    if(hasPathSum(root->left, sum-root->val))
        return true;
    if(hasPathSum(root->right, sum-root->val))
        return true;
    return false;
}


int main(){
    return 0;
}